package simple; /**
 * @projectName study-note
 * @package PACKAGE_NAME
 * @className PACKAGE_NAME.Graph
 */

import java.util.*;
import java.util.stream.Collectors;

/**
 * Graph
 * @description 加权图
 * @author answer_wx
 * @date 2022/7/6 21:32
 * @version 1.0
 */
public class Graph {
    // 正无穷
    static final double positiveInfinity = Double.POSITIVE_INFINITY;
    /**
     * 定义图散列表
     */
    static HashMap<String, HashMap<String, Double>> graph = new HashMap<>();
    /**
     * 创建开销散列表
     */
    static HashMap<String, Double> costs = new HashMap<>();
    /**
     * 创建父节点散列表
     */
    static HashMap<String, String> parents = new HashMap<>();

    /**
     * 记录处理过的节点
     */
    static List<String> process = new ArrayList<String>();


    static {
        /**
         * 初始化图：定义Start,A,B,End 四个点
         *
         * Start->A->End：6+1
         * Start->B->End：2+5
         * Start->B->A->End：2+1+1
         */
        HashMap<String, Double> start = new HashMap<>();
        start.put("A", 6.0);
        start.put("B", 2.0);
        graph.put("Start", start);
        HashMap<String, Double> a = new HashMap<>();
        a.put("End", 1.0);
        graph.put("A", a);
        HashMap<String, Double> b = new HashMap<>();
        b.put("A", 1.0);
        b.put("End", 5.0);
        graph.put("B", b);
    }

    public static String findLowestNode() {
        if (costs.isEmpty()) {
            costs = graph.get("Start");
        }
        List<Map.Entry<String, Double>> list = new ArrayList<>(costs.entrySet());
        list.sort(Comparator.comparing(Map.Entry::getValue));
        Map<String, Double> map2 = new LinkedHashMap<>();
        for (Map.Entry<String, Double> entry : list) {
            map2.put(entry.getKey(), entry.getValue());
        }
        for (String node : map2.keySet()) {
            if (!process.contains(node)) {
                return node;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        String node = findLowestNode();
        while (node != null) {
            if ("End".equals(node)) {
                System.out.println(costs.get("End").intValue());
                return;
            }
            Double cost = costs.get(node);
            HashMap<String, Double> neighbors = graph.get(node);
            for (String key : neighbors.keySet()) {
                Double newCost = cost + neighbors.get(key);
                if (!costs.containsKey(key) || costs.get(key) > newCost) {
                    costs.put(key, newCost);
                    parents.put(key, node);
                }
            }
            process.add(node);
            node = findLowestNode();
        }
    }
}